//package javaTest;
//
//import java.util.ArrayList;
//import java.util.List;
//
//public class BinaryTree {
//    static class TreeNode {
//        public char val;
//        public TreeNode left;//存储做孩子的引用
//        public TreeNode right;//存储右孩子
//
//        public TreeNode (char val){
//            this.val=val;
//        }
//    }
//
//    //创建一个二叉树
//public TreeNode createTree(){
//        TreeNode A=new TreeNode('A');
//        TreeNode B=new TreeNode('B');
//        TreeNode C=new TreeNode('C');
//        TreeNode D=new TreeNode('D');
//        TreeNode E=new TreeNode('E');
//        TreeNode F=new TreeNode('F');
//        TreeNode G=new TreeNode('G');
//        TreeNode H=new TreeNode('H');
//         A.left=B;
//         A.right=C;
//         B.left=D;
//         B.right=E;
//         C.left=F;
//         C.right=G;
//         E.right=H;
//
//         return A;
//}          //前序遍历
//        void preOrder(TreeNode root){
//            if(root==null) return;
//            System.out.println(root.val+" ");
//            preOrder(root.left);
//            preOrder(root.right);
//        }
//        //前序遍历的第一种遍历思路
//    List<Character> list=new ArrayList<>();
//    public List<Character> preorderTraversal(TreeNode root){
//        if(root==null)return list;
//        list.add(root.val);
//        preorderTraversal(root.left);
//        preorderTraversal(root.right);
//        return list;
//    }
//        //子问题思路
//        //前序遍历的另一种写法
//         public List<Character> preOrderTraversal(TreeNode root) {
//             List<Character> list=new ArrayList<>();
//            if(root==null) return list;
//            list.add(root.val);
//
//           List<Character>leftTree= preOrderTraversal(root.left);
//           list.addAll(leftTree);
//            List<Character>rightTree=preOrderTraversal(root.right);
//          list.addAll(rightTree);
//            return list;
//    }
//
//
//    void inOrder(TreeNode root){
//            if(root==null) return;
//            inOrder(root.left);
//            System.out.println(root.val+" ");
//            inOrder(root.right);
//        }
//        //中序遍历的另一种写法
//        public List<Character> inOrderTraversal(TreeNode root) {
//            List<Character> list=new ArrayList<>();
//            if(root==null) return list;
//            list.add(root.val);
//            List<Character>leftTree= inOrderTraversal(root.left);
//            list.addAll(leftTree);
//            List<Character>rightTree=inOrderTraversal(root.right);
//            list.addAll(rightTree);
//            return list;
//        }
//        void postOrder(TreeNode root){
//            if(root==null) return;
//            postOrder(root.left);
//            postOrder(root.right);
//            System.out.println(root.val+" ");
//        }
//        //后序遍历的另一种写法
//        public List<Character> postOrderTraversal(TreeNode root) {
//            List<Character> list=new ArrayList<>();
//            if(root==null) return list;
//            list.add(root.val);
//            List<Character>leftTree= postOrderTraversal(root.left);
//            list.addAll(leftTree);
//            List<Character>rightTree=postOrderTraversal(root.right);
//            list.addAll(rightTree);
//            return list;
//        }
//
//
//
//
//
//
//
////孩子兄弟表示法
//    class Node{
//         int value;
//         Node firstChild;//第一个孩子引用
//         Node nextBrother;//下一个兄弟引用
//    }
//    //孩子表示法
//    class Node1{
//        int val;
//        Node left;
//        Node right;
//    }
//    //孩子双亲表示法
//    class Node3{
//        int val;
//        Node left;
//        Node right;
//        Node parent;
//    }
//    //前序遍历   根-左子树-右子树
//    //中序遍历
//    //后序遍历
//    //层序遍历
//
//
//
//    //获取树当中节点的个数
//    public static int nodeSize (TreeNode root){
//        if(root==null)return 0;
//        return 1+nodeSize(root.left)+nodeSize(root.right);
//    }
//    public static int leafSize;
//    //获取叶子节点的个数,左右都为空的时候
//    public void getLeafNodeCount(TreeNode root){
//        if(root==null)return;
//        if(root.left==null&&root.right==null){
//            leafSize++;
//        }
//        getLeafNodeCount(root.left);
//        getLeafNodeCount(root.right);
//
//    }
//    public int getLeafSizeCount2(TreeNode root){
//        if(root==null) return 0;
//
//        if(root.left==null&&root.right==null){
//            return 1;
//        }
//        return getLeafSizeCount2(root.left)+getLeafSizeCount2(root.right);
//    }
//
//
//
////    public int getKLeveNodeCount(TreeNode root,int k){
////
////    }
//
//
//    //遍历
//    //子问题思路
//    public int getHeight(TreeNode root){
//        if(root==null){
//            return 0;
//        }
//        int leftHeight=getHeight(root.left);
//        int rightHeight=getHeight(root.right);
//
//        return Math.max(leftHeight,rightHeight)+1;
//    }
//
//
//    public TreeNode findVal(TreeNode root,char val){
//        if(root==null) return null;
//        if(root.val==val){
//            return root;
//        }else if(root.left==null){
//                return null;
//            }else{
//            return findVal(root.left,val);
//        }
//
//
//
//
//
//class Solution{
//    public boolean isSameTree(TreeNode p,TreeNode q){
//        //先判断结构是否一样
//        if(p!=null&&q==null||p==null&&q!=null){
//            return false;
//        }
//        //上面没有执行，要吗都为空，要么都不为空
//        if(p==null&&q==null){
//            return true;
//        }
//        if(p.val!=q.val){
//            return false;
//        }
//        //都不为空且值一样
//        return isSameTree(p.left,q.left)&&isSameTree(p.right,q.right);
//    }
//}
////二叉树的子树
//        class Solution2{
//            public boolean isSubTree(TreeNode root,TreeNode subRoot){
//                if(root==null){
//                    return false;
//                }
//
//
//                if(root==null&&subRoot!=null||root!=null&&subRoot==null){
//                    return false;
//                }
//                if(root==null&&subRoot==null){
//                    return true;
//                }
//                if(root.val!=subRoot.val){
//                    return false;
//                }
//
//            }
//        }
//    }
////翻转二叉树
//    class Solutions{
//        public TreeNode invertTree(TreeNode root){
//            if(root==null){
//                return null;//不能反转
//            }
//            TreeNode temp=root.left;
//            root.left=root.right;
//            root.right=temp;//换
//            invertTree(root.left);
//            invertTree(root.right);
//            return root;
//        }
//}
//
//
//
//}//结尾双引号
